import java.util.Stack;

/**
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 * <p>
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 * <p>
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 提示：a + b 意味着字符串 a 和 b 连接。
 * <p>
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出：false
 * 示例 3：
 * <p>
 * 输入：s1 = "", s2 = "", s3 = ""
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(isInterleave("aabcc", "dbbca", "aadbbbaccc"));

    }

    private static int[][] result;

    /**
     * dp
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        result = new int[s1.length() + 1][s2.length() + 1];
        return dp(s1.toCharArray(), 0, s2.toCharArray(), 0, s3.toCharArray(), 0);
    }

    /**
     * dp
     *
     * @param chars1
     * @param p1
     * @param chars2
     * @param p2
     * @param chars3
     * @param p3
     * @return
     */
    public static boolean dp(char[] chars1, int p1, char[] chars2, int p2, char[] chars3, int p3) {
        // 判断结束标志
        if (p3 == chars3.length) {
            return true;
        }
        if (result[p1][p2] != 0) {
            // 1表示真，2表示假
            return result[p1][p2] == 1;
        }
        char c1 = p1 == chars1.length ? '1' : chars1[p1];
        char c2 = p2 == chars2.length ? '1' : chars2[p2];
        char c3 = chars3[p3];
        boolean res = false;
        if (c1 == c2 && c1 == c3) {
            res = dp(chars1, p1 + 1, chars2, p2, chars3, p3 + 1) || dp(chars1, p1, chars2, p2 + 1, chars3, p3 + 1);
        } else if (c1 == c3) {
            res = dp(chars1, p1 + 1, chars2, p2, chars3, p3 + 1);
        } else if (c2 == c3) {
            res = dp(chars1, p1, chars2, p2 + 1, chars3, p3 + 1);
        }
        result[p1][p2] = res ? 1 : 2;
        return res;
    }

    /**
     * 思路的这样子的，把在遍历过程中遇到的有选择的情况都记到栈里面去
     * 性能有点低，是不是考虑用贪心算法
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public static boolean isInterleave1(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        Stack<int[]> stack = new Stack<int[]>();
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        char[] chars3 = s3.toCharArray();
        int p1 = 0, p2 = 0, p3 = 0;
        while (p3 < chars3.length) {
            char c1 = p1 == chars1.length ? '1' : chars1[p1];
            char c2 = p2 == chars2.length ? '1' : chars2[p2];
            char c3 = chars3[p3];
            if (c1 == c2 && c1 == c3) {
                // 如果两个都匹配了，把当前情况加入到堆栈，然后优先选择c1
                int[] possibility = new int[3];
                possibility[0] = p1;
                possibility[1] = p2;
                possibility[2] = p3;
                stack.push(possibility);
                p3++;
                p1++;
            } else if (c1 == c3) {
                p3++;
                p1++;
            } else if (c2 == c3) {
                p3++;
                p2++;
            } else {
                // 如果都没匹配，则回退到堆栈里面的情况
                if (stack.isEmpty()) {
                    return false;
                }
                int[] possibility = stack.pop();
                p1 = possibility[0];
                p2 = possibility[1] + 1;
                p3 = possibility[2] + 1;
            }
        }
        // 如果全部走完了，返回成功
        return true;
    }
}